package fun.codedesign.jdk.util.linkedlist;

public class ZLinkedList<T> {
    // 链表数据，采用静态内部类来进行链表的存储，外部类，只记录其开头与结尾
    private Entry<T> first;
    private Entry<T> end;
    /**
     * 元素数量
     */
    private int size = 0;
    /**
     * 修改次数
     */
    private int modSize = 0;

    public ZLinkedList() {
    }

    /**
     * 增加一个对象：默认是往末位增加
     *
     * @param t
     */
    public void add(T t) {
        // 第一个元素添加，首尾都是它
        if (0 == this.size) {
            Entry<T> newEntry = new Entry<>(t);
            this.first = newEntry;
            this.end = newEntry;
            size++;
            modSize++;
            return;
        }
        // 如果已经存在至少一个元素,那新加的元素就在末位的元素进行连接
        if (size > 0) {
            Entry<T> newEntry = new Entry<>(t);
            newEntry.pre = end.pre;
            end.pre.next = newEntry;
            end = newEntry;
        }
        // 元素数量及修改次数+1
        size++;
        modSize++;
    }

    /**
     * 将元素插入固定位置
     */
    public void add(int index, T t) {
        if (index < 0 || index > (this.size == 0 ? 0 : this.size - 1)) {
            throw new IndexOutOfBoundsException("下标不符合要求");
        }
        Entry<T> newEntry = new Entry<>(t);
        // size =1时，增加的是一个
        if (0 == this.size) {
            this.first = newEntry;
            this.end = newEntry;
            size++;
            modSize++;
            return;
        }

        //如果是从头开始插入，则需要调整first first.next newEntry 三个元素
        // size==1时候不需要调整end
        if (0 == index) {
            newEntry.next = this.first;
            this.first.pre = newEntry;
            // 此处end 与first相同，修改first即修改end
            this.first = newEntry;
            size++;
            modSize++;
            return;
        }
        // 中部插入，则先定位target元素，修改 newEntry target target.pre
        Entry<T> target = getEntry(index);
        newEntry.pre = target.pre.pre;
        newEntry.next = target;
        target.pre.next = newEntry;
        target.pre = newEntry;
        size++;
        modSize++;
    }

    /**
     * 取固定下标位置的元素, next index次即可
     */
    public T get(int index) {
        if (index < 0) {
            throw new IllegalArgumentException();
        }
        Entry<T> target = getEntry(index);
        return target.t;
    }

    /**
     * 移除元素,默认移除最后一位的元素,倒数第二位变成末位
     */
    public void remove() {
        this.end = this.end.pre;
        end.next = end;
        size--;
        modSize++;
    }

    /**
     * 移除固定位置的元素， remove后需要对 target.pre target.next进行调整
     */
    public T remove(int index) {
        Entry<T> target = getEntry(index);
        target.pre.next = target.next;
        target.next.pre = target.pre;
        if (0 == index) {
            first = first.next;
        }
        size--;
        modSize++;
        return target.t;
    }

    /**
     * 返回元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }

    /**
     * 清空所有的元素
     */
    public void clear() {
        this.first = null;
        this.end = null;
        size = 0;
        modSize = 0;
    }

    /**
     * 取得固定位置的元素包装类Entry, next index次即可
     */
    private Entry<T> getEntry(int index) {
        if (index < 0) {
            throw new IllegalArgumentException();
        }
        // index 为0的情况下返回first
        Entry<T> target = this.first;
        Entry<T> temp = this.first;

        for (int i = 0; i < index; i++) {
            target = temp.next;
            temp = target;
        }
        return target;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(100);
        Entry<T> element;
        for (int i = 0; i < size; i++) {
            element = getEntry(i);
            sb.append(element.t.toString());
            if (i != size - 1) {
                sb.append(",");
            }
        }
        return sb.toString();
    }

    private static class Entry<T> {
        T t;
        Entry<T> pre;
        Entry<T> next;

        /**
         * 初始构造时,pre及next节点==自己
         *
         * @param t
         */
        public Entry(T t) {
            this.t = t;
            this.pre = this;
            this.next = this;
        }

        /**
         * 可以确认上一节点，自己是最后一节点
         *
         * @param t
         * @param pre
         */
        // public Entry(T t, Entry<T> pre, Entry<T> next) {
        //     this.t = t;
        //     this.pre = pre;
        //     this.next = next;
        // }
    }
}
